#include<bits/stdc++.h>

using namespace std;
int a[50][50] = {
        {7, 0, 0, 0, 0},
        {3, 8, 0, 0, 0},
        {8, 1, 0, 0, 0},
        {2, 7, 4, 4, 0},
        {4, 5, 2, 6, 5},
};
int dp[50][50];
int n = 5;

//记忆化搜索改进递归效率 ，从O(2^n)下降到O(n^2)
int maxSum(int i, int j) {
    if (dp[i][j] != 0)return dp[i][j];//先查表，如果计算过就直接返回答案
    if (i == n - 1) {
        return dp[i][j] = a[i][j];//算出来及时写到dp数组中
    }
    int x = maxSum(i + 1, j);
    int y = maxSum(i + 1, j + 1);

    return dp[i][j] = a[i][j] + max(x, y);//算出来及时写到dp数组中
}

int main() {
    cout << maxSum(0, 0);
}
